class SortDemo:
    def sort_bubble(self, alist):
        """冒泡排序 时间复杂度O(n^2) 空间复杂度O(1)"""
        n = len(alist)
        # 控制遍历的次数
        for i in range(n - 1):  # 排列n-1次
            # 一般情况下稳定
            # O(n^2)
            flag = False
            # 控制角标移动  # 一次循环最大比较n-1次，最高角标递减
            for j in range(n - 1 - i):
                if alist[j] > alist[j + 1]:
                    alist[j], alist[j + 1] = alist[j + 1], alist[j]
                    flag = True
            # 如果已经有序，直接退出循环
            if not flag:
                break

    def sort_insert(self, alist):
        """插入排序 时间复杂度O(n^2) 空间复杂度O(1)"""
        n = len(alist)
        # 控制遍历的次数
        for i in range(1, len(alist)):  # 从第二个位置开始插入,
            # 控制角标移动
            # 最大角标递增,交换元素位置
            for j in range(i, 0, -1):
                if alist[j] < alist[j - 1]:
                    alist[j], alist[j - 1] = alist[j - 1], alist[j]

    def sort_merge(self, alist):
        """归并排序 时间复杂度O(nlogn) 空间复杂度O(n)"""
        n = len(alist)
        if n <= 1:
            return alist

        m = n // 2
        # 二分
        llist = self.sort_merge(alist[:m])
        rlist = self.sort_merge(alist[m:])

        left = 0
        right = 0
        sorted_list = []
        l_len = len(llist)
        r_len = len(rlist)
        while left < l_len and right < r_len:
            if llist[left] <= rlist[right]:
                sorted_list.append(llist[left])
                left += 1
            else:
                sorted_list.append(rlist[right])
                right += 1
        sorted_list.extend(llist[left:])
        sorted_list.extend(rlist[right:])
        return sorted_list

    def sort_quick(self, alist, start, end):
        """快速排序 时间复杂度O(nlogn) 空间复杂度O(logn)"""
        """排序终止条件"""
        if start >= end:
            return

        mid = alist[start]
        low = start
        high = end
        while low < high:
            while low < high and alist[high] >= mid:
                high -= 1
            alist[low] = alist[high]
            while low < high and alist[low] < mid:
                low += 1
            alist[high] = alist[low]

        alist[low] = mid
        self.sort_quick(alist, start, low - 1)
        self.sort_quick(alist, low + 1, end)

    def sort_select(self, alist):
        """选择排序 时间复杂度O(n^2) 空间复杂度O(1)"""
        n = len(alist)

        # 控制遍历的次数
        for i in range(n - 1):  # 排列n-1次
            min_index = i
            # 控制角标移动  # 每次循环找到最小元素的位置，最小角标递增
            for j in range(i, n):
                if alist[j] < alist[min_index]:
                    min_index = j
            # 交换元素位置
            if min_index != i:
                alist[i], alist[min_index] = alist[min_index], alist[i]

    def sort_shell(self, alist):
        """希尔排序 时间复杂度O(n(logn)^2) 空间复杂度O(1)"""
        n = len(alist)
        # 控制间隙
        gap = n // 2
        while gap > 0:
            # 控制排序次数
            for i in range(gap, n):
                j = i
                # 控制比较次数
                while j >= gap and alist[j - gap] > alist[j]:
                    alist[j - gap], alist[j] = alist[j], alist[j - gap]
                    j -= gap
            # 每次间隙减半
            gap //= 2

    def _test_sort_bubble(self):
        """
        sd = SortDemo()
        sd._test_sort_bubble()
        """
        li = [11, 22, 3, 77, 66, 88]
        sd = SortDemo()
        sd.sort_bubble(li)
        print(li)

    def _test_sort_insert(self):
        """
        sd = SortDemo()
        sd._test_sort_insert()
        """
        li = [11, 22, 3, 77, 66, 88]
        sd = SortDemo()
        sd.sort_insert(li)
        print(li)

    def _test_sort_merge(self):
        """
        sd = SortDemo()
        sd._test_sort_merge()
        """
        li = [11, 22, 3, 77, 66, 88]
        sd = SortDemo()
        print(sd.sort_merge(li))

    def _test_sort_quick(self):
        """
        sd = SortDemo()
        sd._test_sort_quick()
        """
        li = [11, 22, 3, 77, 66, 88]
        sd = SortDemo()
        sd.sort_quick(li, 0, len(li) - 1)
        print(li)

    def _test_sort_select(self):
        """
        sd = SortDemo()
        sd._test_sort_select()
        """
        li = [11, 22, 3, 77, 66, 88]
        sd = SortDemo()
        sd.sort_select(li)
        print(li)

    def _test_sort_shell(self):
        """
        sd = SortDemo()
        sd._test_sort_shell()
        """
        sd = SortDemo()
        li = [11, 22, 3, 77, 66, 88]
        sd.sort_shell(li)
        print(li)
        li = [2, 1, 3, 4]
        sd.sort_shell(li)
        print(li)


if __name__ == '__main__':
    sd = SortDemo()
    sd._test_sort_shell()